package com.Questions.DP;


/**
 * 最长递增子序列
 */
public class leetcode300 {
    public int lengthOfLIS(int[] nums) {
        // 设dp[i] 是以i为结尾的 最长递增子序列的长度
        // nums[i]>nums[j] dp[i]=dp[j]+1
        int[] dp=new int[nums.length];
        dp[0]=1;
        int ans=0;
        for(int i=1;i<nums.length;++i){
            int max=0;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    max=Math.max(max,dp[j]);
                }
            }
            dp[i]=max+1;
            ans=Math.max(ans,dp[i]);
        }
        return ans;

    }
}
